package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author qidi
 * @date 2022-01-17 14:08:23
 */
class Q0145_BinaryTreePostorderTraversal {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            if (root == null) return ans;

            Deque<TreeNode> stack = new ArrayDeque<>();
            Deque<TreeNode> stackHead = new ArrayDeque<>();
            stack.push(root);

            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                stackHead.push(node);
                if (node.left != null) stack.push(node.left);
                if (node.right != null) stack.push(node.right);
            }

            while (!stackHead.isEmpty()) {
                ans.add(stackHead.pop().val);
            }

            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0145_BinaryTreePostorderTraversal().new Solution();
        BTreeUtil util = BTreeUtil.getInstance();
        System.out.println(solution.postorderTraversal(util.generateFromArray(1, null, 2, 3)));
        System.out.println(solution.postorderTraversal(util.generateFromArray(1)));
        System.out.println(solution.postorderTraversal(util.generateFromArray()));
        System.out.println(solution.postorderTraversal(util.generateFromArray(1, 2)));
        System.out.println(solution.postorderTraversal(util.generateFromArray(1, null, 2)));
        System.out.println(solution.postorderTraversal(util.generateFromArray(1, 2, 3, 4, 5, 6, 7)));
        System.out.println(solution.postorderTraversal(util.generateFromArray(1, 2, 3, null, 4, 5, 6)));
    }
}